contents

✨ 코딩 테스트를 위한 문자열 알고리즘 정리

코딩 테스트나 기술 인터뷰에서 매우 자주 등장하는 문자열 알고리즘을 다음과 같이 핵심 개념, 대표 유형별 설명, 자바 코드 예제와 함께 정리했습니다.

1. 🔎 패턴 검색 알고리즘

a. Naive(기본) 문자열 검색

텍스트의 각 위치에서 패턴의 모든 문자를 하나씩 비교하는 단순한 방식

int naiveSearch(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text.charAt(i + j) == pattern.charAt(j)) j++;
        if (j == m) return i; // 패턴 찾음
    }
    return -1;
}

• 시간 복잡도: O(n × m) → 짧은 문자열엔 괜찮음

b. KMP (Knuth-Morris-Pratt) 알고리즘

패턴 내 접두사 일치 정보를 사용하여 중복 비교 없이 빠르게 찾는 알고리즘

void kmpSearch(String text, String pat) {
    int[] lps = computeLPSArray(pat);
    int i = 0, j = 0;
    while (i < text.length()) {
        if (pat.charAt(j) == text.charAt(i)) {
            i++; j++;
        }
        if (j == pat.length()) {
            System.out.println("Found at " + (i - j));
            j = lps[j - 1];
        } else if (i < text.length() && pat.charAt(j) != text.charAt(i)) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
}

LPS 배열 계산 함수:

int[] computeLPSArray(String pat) {
    int len = 0, i = 1;
    int[] lps = new int[pat.length()];
    lps[0] = 0;
    while (i < pat.length()) {
        if (pat.charAt(i) == pat.charAt(len))
            lps[i++] = ++len;
        else if (len != 0)
            len = lps[len - 1];
        else
            lps[i++] = 0;
    }
    return lps;
}

• 시간 복잡도: O(n + m)
• 문자열이 길거나 여러 번 매칭할 때 매우 효율적

c. Rabin-Karp 알고리즘 (롤링 해시 방식)

문자열과 패턴을 해싱한 뒤, 해시값을 비교하여 빠르게 위치 찾기

int rabinKarp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    int base = 256, mod = 101;
    int patHash = 0, txtHash = 0, h = 1;

    for (int i = 0; i < m - 1; i++) h = (h * base) % mod;
    for (int i = 0; i < m; i++) {
        patHash = (base * patHash + pattern.charAt(i)) % mod;
        txtHash = (base * txtHash + text.charAt(i)) % mod;
    }

    for (int i = 0; i <= n - m; i++) {
        if (patHash == txtHash && text.substring(i, i + m).equals(pattern)) return i;
        if (i < n - m) {
            txtHash = ((base * (txtHash - text.charAt(i) * h)) + text.charAt(i + m)) % mod;
            if (txtHash < 0) txtHash += mod;
        }
    }
    return -1;
}

2. 🌱 접미사 배열(Suffix Array) & 접미사 트리

• 모든 접미사를 정렬하여 구성 (문자열 내 존재 여부, 반복 탐색 등에서 매우 유용)
• Suffix Array: 공간 효율형
• Suffix Tree: 고급 알고리즘, 빠른 질의 응답 지원

활용 예:

• 서브스트링 존재 확인
• 가장 긴 반복 문자열 찾기
• 사전 순 비교

3. 🌳 트라이(Trie) 자료구조

문자열을 접두사별로 저장하는 Tree 구조
→ 사전 검색, 자동완성, prefix 검색

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    boolean isWord = false;
}
class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.next[idx] == null) curr.next[idx] = new TrieNode();
            curr = curr.next[idx];
        }
        curr.isWord = true;
    }

    boolean search(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.next[idx] == null) return false;
            curr = curr.next[idx];
        }
        return curr.isWord;
    }
}

4. 🪞 팰린드롬 문자열 관련 알고리즘

a. 가장 긴 팰린드롬 부분 문자열 (Expand Around Center)

중심에서 좌우로 확장하며 가장 긴 대칭 구간을 찾는 방식

String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expand(s, i, i);       // 홀수
        int len2 = expand(s, i, i + 1);   // 짝수
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

5. 🧩 공통 접두사(Prefix) 찾기

여러 문자열 중 가장 긴 공통 접두사 반환

String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        while (!strs[i].startsWith(prefix)) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

6. 🧮 문자열 관련 DP – Edit Distance (편집 거리)

문자열 A를 B로 바꾸기 위한 최소 연산 횟수 (삽입/삭제/치환)

int editDistance(String a, String b) {
    int[][] dp = new int[a.length()+1][b.length()+1];
    for (int i = 0; i <= a.length(); i++)
        for (int j = 0; j <= b.length(); j++) {
            if (i == 0) dp[i][j] = j;
            else if (j == 0) dp[i][j] = i;
            else if (a.charAt(i-1) == b.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + Math.min(dp[i-1][j-1],
                               Math.min(dp[i-1][j], dp[i][j-1]));
        }
    return dp[a.length()][b.length()];
}

7. 🎯 슬라이딩 윈도우 & 투 포인터 기법

패턴 포함/빈도수 기준 최소 윈도우 찾기 등의 문제에 자주 사용

🔹 최소 윈도우 부분 문자열

String minWindow(String s, String t) {
    int[] count = new int[128];
    for (char c : t.toCharArray()) count[c]++;
    int left = 0, right = 0, minLen = Integer.MAX_VALUE, minStart = 0, required = t.length();
    while (right < s.length()) {
        if (count[s.charAt(right++)]-- > 0) required--;
        while (required == 0) {
            if (right - left < minLen) {
                minLen = right - left;
                minStart = left;
            }
            if (count[s.charAt(left++)]++ == 0) required++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

8. 기타 문자열 문제 유형

• 단어/문자열 뒤집기
• 정규표현식 기반 검증 (이메일, 아이디 유효성)
• 가장 긴 반복 부분 수열 (DP와 자주 연결)
• 아나그램 판별 (정렬 or 알파벳 카운트)

✅ 요약 테이블: 문자열 대표 알고리즘

💡 실전 팁

• KMP, Trie는 반드시 직접 구현해봐야 합니다.
• 슬라이딩 윈도우 유형은 길이나 빈도 조건 기준 substring 문제에 탁월합니다.
• 문자열 관련 DP(편집 거리, 공통 부분 수열 등)는 자주 나옵니다. 상태 정의 + 점화식 구축 연습 필수!
• 유니코드/공백/특수 문자 처리 등도 면접 때 묻는 경우가 있으니 대비하세요.

💡 주요 문자열 알고리즘 – 고급 단계별 동작 (Dry Run 예제 중심)

코딩 테스트와 인터뷰에서 자주 나오는 문자열 알고리즘들의 동작 순서를 예제와 함께 한 단계씩 설명한 내용입니다. 내부 변수 변화, 반복 흐름, 데이터 구조 업데이트 과정을 보여줍니다.

1. 🔁 KMP (Knuth–Morris–Pratt) 패턴 검색 알고리즘

문제: 문자열 "ABABC"를 "ABABDABACDABABCABAB"에서 찾기

📌 1단계: LPS(LPS: Longest Prefix which is Suffix) 배열 생성

패턴 "ABABC"

• 인덱스: 0 1 2 3 4
• 문자: A B A B C

LPS 생성 과정:

➡️ 결과: LPS 배열 = ab

📌 2단계: 본문 텍스트 탐색 (i: 텍스트, j: 패턴)

텍스트 "ABABDABACDABABCABAB"

➡️ 결과: 패턴 "ABABC"은 텍스트 내 인덱스 8에서 매칭됨.

2. 🌳 Trie(트라이) 삽입 & 검색 Dry Run

입력 단어: apple, app, bat
검색: "app"

INSERT

• "apple" → a → p → p → l → e (isWord=true)
• "app" → a → p → p (isWord=true)
• "bat" → b → a → t (isWord=true)

SEARCH "app"

• a → 존재
• p → 존재
• p → 존재 + isWord = true ✅
  → "app" 존재함

3. 📚 Sliding Window – 최소 윈도우 부분 문자열

문제: S="ADOBECODEBANC", T="ABC"

모든 ‘A’, ‘B’, ‘C’를 포함하는 최소 윈도우 찾기

진행 요약:

➡️ 결과: 최소 윈도우 = "BANC"

4. 🧮 편집 거리(Edit Distance) DP Dry Run

문자열: "horse" → "ros"로 바꾸는 최소 연산 수

편집 연산: 삽입, 삭제, 교체

DP 테이블 생성 (dp[i][j] = horse[0~i] → ros[0~j]의 최소 연산)

🟩 최종 답: 편집 거리 = 3

(예: horse → rorse → rose → ros)

✅ 요약 정리

references